﻿/// <summary>
/// https://leetcode-cn.com/problems/unique-paths-ii/
/// </summary>
public class Solution
{
    private T GetOrDefault<T>(T[,] values, int index1, int index2, T defaultVaue)
    {
        if (index1 >= 0 && index1 < values.GetLength(0)
            && index2 >= 0 && index2 < values.GetLength(1))
        {
            return values[index1, index2];
        }
        else
            return defaultVaue;
    }

    public int UniquePathsWithObstacles(int[][] obstacleGrid)
    {
        int[,] resultMap = new int[obstacleGrid.Length, obstacleGrid[0].Length];
        bool continuing = true;
        for (int i = 0; continuing; i++)
        {
            continuing = i < resultMap.GetLength(0);
            if (continuing)
            {
                for (int j = 0; j < resultMap.GetLength(1); j++)
                {
                    if (obstacleGrid[i][j] == 1)
                        resultMap[i, j] = 0;
                    else if (i is 0 && j is 0)
                        resultMap[i, j] = 1;
                    else
                        resultMap[i, j] =
                            this.GetOrDefault(resultMap, i - 1, j, 0) +
                            this.GetOrDefault(resultMap, i, j - 1, 0);
                }
            }

            if (i < resultMap.GetLength(1))
            {
                continuing = true;
                for (int j = 0; j < resultMap.GetLength(0); j++)
                {
                    if (obstacleGrid[j][i] == 1)
                        resultMap[j, i] = 0;
                    else if (i is 0 && j is 0)
                        resultMap[j, i] = 1;
                    else
                        resultMap[j, i] =
                            this.GetOrDefault(resultMap, j - 1, i, 0) +
                            this.GetOrDefault(resultMap, j, i - 1, 0);
                }
            }
        }
        return resultMap[resultMap.GetLength(0) - 1, resultMap.GetLength(1) - 1];
    }
}

/* 下方案超时
/// <summary>
/// https://leetcode-cn.com/problems/unique-paths-ii/
/// </summary>
public class Solution
{
    private class Map
    {
        public record Position(int X, int Y);

        private readonly bool[,] map;

        public int XLength => map.GetLength(1);
        public int YLength => map.GetLength(0);

        public Position Robot { get; private set; }
        public bool HasObstaclesAt(Position position)
        {
            return map[position.Y, position.X];
        }

        public bool TryMoveDown()
        {
            var newY = Robot.Y + 1;
            if (YLength <= newY)
                return false;

            var newPosition = Robot with { Y = newY };
            if (HasObstaclesAt(newPosition))
                return false;

            Robot = newPosition;
            return true;
        }

        public bool TryMoveRight()
        {
            var newX = Robot.X + 1;
            if (XLength <= newX)
                return false;

            var newPosition = Robot with { X = newX };
            if (HasObstaclesAt(newPosition))
                return false;

            Robot = newPosition;
            return true;
        }

        public Map MakeCopy()
        {
            return new Map(map, Robot);
        }
        private Map(bool[,] map, Position robot)
        {
            Robot = robot;
            this.map = map;
        }

        public Map(int[][] obstacleGrid)
        {
            var yLength = obstacleGrid.Length;
            var xLength = obstacleGrid[0].Length;
            map = new bool[yLength, xLength];
            for (int i = 0; i < yLength; i++)
            {
                for (int j = 0; j < xLength; j++)
                    map[i, j] = obstacleGrid[i][j] == 1;
            }
            Robot = new Position(0, 0);
        }
    }

    public int UniquePathsWithObstacles(int[][] obstacleGrid)
    {
        IEnumerable<Map> GetNextSteps(Map map)
        {
            var copy = map.MakeCopy();
            if (copy.TryMoveDown())
                yield return copy;
            if (map.TryMoveRight())
                yield return map;
        }

        IEnumerable<Map> maps;
        int count;
        {
            var ori = new Map(obstacleGrid);
            if (ori.HasObstaclesAt(ori.Robot))
                return 0;

            maps = Enumerable.Repeat(ori, 1);
            count = ori.XLength + ori.YLength - 2;
        }

        for (int i = 0; i < count; i++)
            maps = maps.SelectMany(GetNextSteps);

        return maps.Count();
    }
}
*/